__author__ = 'wenke1'

import random
'''
#this is a quick sort program
1.select a key
2.compare the key,and split the arry into two part
3.repeat the step2
'''
def quicksortpos(a,low,high):
    key = a[low]
    while (low<high):
        while low<high and a[high]>=key:
            high=high-1
        a[low] = a[high]
        while low<high and a[low]<=key:
            low =  low+1
        a[high] = a[low]
        if low==high:
            a[low] = key
            pos = low
            print 'pos is:', pos
	    break
    return pos

def quicksort(a,low,high):
    if low < high:
        pos =  quicksortpos(a,low,high)
        quicksort(a,low,pos-1)
	quicksort(a,pos+1,high)
    return a

if __name__=="__main__":
    length = 4
    array = range(length)
    #random create an array
    for i in range(length):
        array[i]=random.randint(1,100)
    print array
    a = quicksort(array,0,length-1)
    print a


